﻿//******************************************//
//        I. BÀI TOÁN SỐ NGUYÊN TỐ          //
//******************************************//

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
using System.Collections;

namespace Chuong4
{
    class SoNguyenTo
    {
        //Khởi tạo Random một số nguyên lớn
        public BigInteger Random(BigInteger min, BigInteger max)
        {
            byte[] maxBytes = max.ToByteArray();
            BitArray maxBits = new BitArray(maxBytes);
            Random random = new Random(DateTime.Now.Millisecond);

            for (int i = 0; i < maxBits.Length; i++)
            {
                // Lấy ngẫu nhiên các bits
                int randomInt = random.Next();
                if ((randomInt % 2) == 0)
                {
                    // Đảo ngược các bits
                    maxBits[i] = !maxBits[i];
                }
            }

            BigInteger result = new BigInteger();

            // Chuyển các bits về số lớn
            for (int k = (maxBits.Count - 1); k >= 0; k--)
            {
                BigInteger bitValue = 0;

                if (maxBits[k])
                {
                    bitValue = BigInteger.Pow(2, k);
                }

                result = BigInteger.Add(result, bitValue);
            }

            // Generate the random number
            BigInteger randomBigInt = BigInteger.ModPow(result, 1, BigInteger.Add(max, min));
            return randomBigInt;
        }

        // Tính X^Y mod N
        public BigInteger ModLuyThua(BigInteger coso, BigInteger somu, BigInteger sochia)
        {
            BigInteger kq = 1;
            while (somu > 0)
            {
                if (somu % 2 == 1)
                    kq = (kq * coso) % sochia;
                somu = somu / 2;
                coso = (coso * coso) % sochia;
            }
            return kq;
        }

        //Kiểm tra một số có phải là nguyên tố hay ko bằng phương pháp thông thường
        public bool isPrimes(BigInteger n)
        {
            if (n <= 1) return false;
            if (n <= 3) return true;
            if (n % 2 == 0 || n % 3 == 0) return false;
            BigInteger s =(BigInteger)(Math.Sqrt((double)n));
            for (BigInteger i = 5; i <= s; i += 6)
            {
                if (n % i == 0 || n % (i + 2) == 0) return false;
            }
            return true;
        }

        //Phép thử Miller
        bool Miller(BigInteger n, BigInteger b)
        {
            BigInteger y = (n - 1);
            bool check = false;
            while (y % 2 == 0)
            {
                y /= 2;
                BigInteger temp = ModLuyThua(b, y, n);
                if (temp != 1 && temp != n - 1)
                    return false;
                if (temp == n - 1) return true;
                if (temp == 1) check = true;
            }

            return check;
        }

        //Phép thử Rabbin_Miller
        public bool Rabin_Miller(BigInteger n, BigInteger q)
        {
            while (q-- > 0)
            {
                BigInteger b = Random(2, n - 1);
                if (!Miller(n, b))
                    return false;
            }
            return true;
        }

        // Tạo một số nguyên tố lớn
        public BigInteger Creat()
        {
            BigInteger s = Random(100000000, 1000000000);
            if (s % 2 == 0) s--;
            while (!isPrimes(s)) s += 2;
            BigInteger t = Random(100000000, 1000000000);
            if (t % 2 == 0) t--;
            while (!isPrimes(t)) t += 2;
            BigInteger i = Random(100000000, 1000000000);
            BigInteger r =  2 * i * t + 1;
            while (!Rabin_Miller(r, 100))
            {
                i++;
                r = 2 * t * i + 1; 
            }

            BigInteger z = ModLuyThua(s, r - 1, r);
            BigInteger psao = 2 * z * s - 1;
            BigInteger k = Random(10000000000,1000000000000);
            BigInteger p = psao + 2 * k * r * s;
            while (!Rabin_Miller(p, 100))
            {
                k++;
                p = psao + 2 * k * r * s;
            }
            return p;
        }
        
    }
}
